#include<iostream>
#include<stdexcept>


template<typename T>
class MyList{
public:
    template <typename L>
    friend std::ostream &operator<<(std::ostream &os, const MyList<L> &pt);

private:

    struct Node{
        T data;      // 数据
        Node *next;  // 指向下一个结点
        Node *prev;  // 指向上一个结点

        Node(const T &value, Node *nextNode = nullptr, Node * prevNode = nullptr
        ):data(value), next(nextNode), prev(prevNode){}
    };

    Node *head;
    Node *tail;
    size_t size;


public:

    MyList():head(nullptr), tail(nullptr), size(0){}

    ~MyList(){clear();}

    // 
    void push_back(const T &value)
    {
        Node *newNode = new Node(value, nullptr, tail);

        if(tail == nullptr){
            head = newNode;
        }else{
            tail->next = newNode;
        }

        tail = newNode;
        size++;

    }

    void push_front(const T &value)
    {
        Node *newNode = new Node(value, head, nullptr);
        
        if(head == nullptr){
            head = newNode;
        }else{
            head->prev = newNode;
        }
        head = newNode;
    }

    void clear()
    {
        while(head){
            Node *temp = head;
            head = head->next;
            delete temp;
        }

        tail = nullptr;
        size = 0;
    }

    size_t getSize() const
    {
        return size;
    }

    // 访问链表中元素
    T &operator[](size_t index) 
    {
        Node *curr = head;

        for(int i = 0;i < index;++i){
            if(!curr){
                throw std::out_of_range("Index out of range");
            }
            curr = curr->next;
        }

        return curr->data;
    }

    // 访问链表中元素
    const T &operator[](size_t index) const
    {
        Node *curr = head;

        for(int i = 0;i < index;++i){
            if(!curr){
                throw std::out_of_range("Index out of range");
            }
            curr = curr->next;
        }

        return curr->data;
    }

    void pop_back()
    {
        if(size > 0){
            Node *oldTail = tail;
            tail = oldTail->prev;
            delete oldTail;

            if(tail){
                tail->next = nullptr;
            }else{
                head = nullptr;
            }
            --size;
        }     
    }

    void pop_front()
    {
        if(size > 0){
            Node *oldHead = head;
            head = oldHead->next;
            delete oldHead;

            if(head){
                head->prev = nullptr;
            }else{
                tail = nullptr;
            }

            --size;
        }
    }


    // 获取指定的节点
    Node *getNode(const T &val)
    {
        Node *curr = head;

        while(curr != nullptr && curr->data != val){
            curr = curr->next;
        }

        return curr;
    }

    T *find(const T &val)
    {
        Node *node = getNode(val);

        if(!node){
            return nullptr;
        }

        return &node->data;
    }

    void remove(const T &val)
    {
        Node *node = getNode(val);

        if(!node) return;

        if(node != head && node != tail){
            // 既不是头节点也不是尾节点
            node->prev->next = node->next;
            node->next->prev = node->prev;
        }
        else if(node == head && node == tail){
            head = nullptr;
            tail = nullptr;
        }
        else if(node == head){
            head = node->next;
            head->prev = nullptr;
        }else{
            tail = node->prev;
            tail->next = nullptr;
        }

        --size;

        delete node;
        node = nullptr;
    }


    void empty() const{return size == 0;}

    Node *begin()
    {
        return head;
    }

    Node *end()
    {
        return nullptr;
    }

    const Node *begin() const
    {
        return head;
    }

    const Node *end() const 
    {
        return nullptr;
    }

    void printElements const()
    {
        for(template MyList<T>::Node curr = head;curr;curr = curr->next){
            std::cout << curr->data << " ";
        }

        std::cout << std::endl;
    }

};

template<typename T>
std::ostream &operator<<(std::ostream &os, const MyList<T> &pt)
{
    for(typename MyList<T>::Node *curr = pt.head;curr;curr = curr->next){
        os << curr->data << " ";
    }
    os << std::endl;
    return os;
}


